class AnimalShelf {
    queue<pair<int,int>> dog;
    queue<pair<int,int>> cat;
    int idx;
public:
    AnimalShelf() {}

    void enqueue(vector<int> animal) {
        if (cat.size() + dog.size() >= 20000)
            return;
        if (animal[1] == 1) {
            dog.push({animal[0],idx++});
        } else {
            cat.push({animal[0],idx++});
        }
    }

    vector<int> dequeueAny() {
        if (cat.empty() && dog.empty()) {
            return {-1, -1};
        } else if (cat.size() && dog.empty()) {
            vector<int> ret;
            ret.push_back(cat.front().first);
            ret.push_back(0);
            cat.pop();
            return ret;
        } else if (cat.empty() && dog.size()) {
            vector<int> ret;
            ret.push_back(dog.front().first);
            ret.push_back(1);
            dog.pop();
            return ret;
        } else {
            vector<int> ret;
            if (dog.front().second< cat.front().second) {
                ret.push_back(dog.front().first);
                ret.push_back(1);
                dog.pop();
            } else {
                ret.push_back(cat.front().first);
                ret.push_back(0);
                cat.pop();
            }
            return ret;
        }
    }

    vector<int> dequeueDog() {
        if (dog.size()) {
            vector<int> ret;
            ret.push_back(dog.front().first);
            ret.push_back(1);
            dog.pop();
            return ret;
        } else {
            return {-1, -1};
        }
    }

    vector<int> dequeueCat() {
        if (cat.size()) {
            vector<int> ret;
            ret.push_back(cat.front().first);
            ret.push_back(0);
            cat.pop();
            return ret;
        }
        else{
            return {-1,-1};
        }
    }
};

/**
 * Your AnimalShelf object will be instantiated and called as such:
 * AnimalShelf* obj = new AnimalShelf();
 * obj->enqueue(animal);
 * vector<int> param_2 = obj->dequeueAny();
 * vector<int> param_3 = obj->dequeueDog();
 * vector<int> param_4 = obj->dequeueCat();
 */
